package avl.non_recursion;

/**
 * AVL 树，对节点的各种操作
 *
 * @author xing
 */
public class AVLTree<V extends Comparable<V>> {

    Node<V> root;

    public AVLTree(Node<V> root) {
        this.root = root;
    }

    public Node<V> getRoot() {
        return root;
    }

    public AVLTree() {
    }

    public void deleteElement(V element) {
        if (element == null) {
            return;
        }
        deleteNode(new Node<>(element));
    }

    private void deleteNode(Node<V> deleteNode) {
        this.root = deleteNode(this.root, deleteNode);
    }

    public Node<V> mergeTwoTree(Node<V> left, Node<V> right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        // 都不为 Null
        // 右边更高
        // 我这里是看谁高，但是在 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 中，
        // 我发现却是就取左子树最大值，再从这个最大值往父节点判断平衡，代码量却实是更少了
//        if (left.getHeight() < right.getHeight()) {
//            Node<V> rleft = right;
//            while (rleft.getLeft() != null) {
//                rleft = rleft.getLeft();
//            }
//             相当于删除了 rleft ，它其可能有一个右子节点，要给它其父节点，并要往它的父节点走，判断平衡，平衡树
//             这里 获取了 right ，要在下边修改 right 之前
//            rleft.getParent().setLeft(rleft.getRight());
//             别玩了设置父节点
//             不要忘记，rleft.right 可能为空
//            if (rleft.getRight() != null) {
//                rleft.getRight().setParent(rleft.getParent());
//            }
//
//            rleft.setLeft(left);
//            rleft.setRight(right);
//             别忘了修改父节点
//            left.setParent(rleft);
//            right.setParent(rleft);
//            Node<V> nodeParent;
//             rleft 要作为新根节点，所以要从原来的 parent 开始~~网~~往上判断
//            Node<V> node = rleft.getParent();
            // 感觉上这里应该链式重新计算一下高度，这不~~想~~像 rotate 方法，会一直（循环）到跟节点都会过一遍去重新计算
            // 应该从父节点链式重新计算
            // rleft.reComputerHeight();
            // 链式之前注意父节点设空，不然会循环（在此之前还有对其父节点的获取与并赋值）
//            rleft.setParent(null);
//            node.chainedReComputerHeight();
            // 这里的父节点别忘了设置为 null，两子树的 merge，不要一循环跑外边去了
//            while ((nodeParent = node.getParent()) != null) {
//                node = rotateInDelete(node);
//                if (nodeParent.getElement().compareTo(node.getElement()) < 0) {
//                    nodeParent.setRight(node);
//                } else {
//                    nodeParent.setLeft(node);
//                }
//                nodeParent.reComputerHeight();
//                node.setParent(nodeParent);
//                node = node.getParent();
//            }
//            node = rotateInDelete(node);
//            return node;
//        } else {
            // 左边更高
            Node<V> lright = left;
            while (lright.getRight() != null) {
                lright = lright.getRight();
            }
            // 相当于删除了 lright ，它其可能有一个~~做~~左子节点，要给它其父节点，并要往它的父节点走，判断平衡，平衡树
            // 这里获取了 left ，要在下边修改 left 之前
            lright.getParent().setRight(lright.getLeft());
            // 不要忘了设置它的父节点, bu 要 忘记可能为空
            if (lright.getLeft() != null) {
                lright.getLeft().setParent(lright.getParent());
            }

            lright.setLeft(left);
            lright.setRight(right);
            left.setParent(lright);
            right.setParent(lright);
            // 不对，应该是从 parent 链式重新计算
            // lright.reComputerHeight();
            Node<V> nodeParent;
            Node<V> node = lright.getParent();
            // 感觉上这里应该链式重新计算一下高度，这不~~想~~像 rotate 方法，会一直（循环）到跟节点都会过一遍去重新计算
            // 链式计算前 lright 父节点设空，否则会循环
            lright.setParent(null);
            node.chainedReComputerHeight();
            while ((nodeParent = node.getParent()) != null) {
                node = rotateInDelete(node);
                if (nodeParent.getElement().compareTo(node.getElement()) < 0) {
                    nodeParent.setRight(node);
                } else {
                    nodeParent.setLeft(node);
                }
                nodeParent.reComputerHeight();
                node.setParent(nodeParent);
                node = nodeParent;
            }
            node = rotateInDelete(node);
            return node;
//        }
    }

    public Node<V> mergeTwoTreebyparent(Node<V> parent) {
        return mergeTwoTree(parent.getLeft(), parent.getRight());
    }

    /**
     * 删除节点
     *
     * @param root       根节点
     * @param deleteNode 要删除的节点
     * @return 删除节点后的树的根节点
     */
    private Node<V> deleteNode(Node<V> root, Node<V> deleteNode) {
        if (root == null || deleteNode == null) {
            return root;
        }
        // 要删除的是根节点
        if (deleteNode.getElement().compareTo(root.getElement()) == 0) {
            // 合并返回
            return mergeTwoTreebyparent(root);
        }
        Node<V> node = root;
        Node<V> parent = null;
        // 遍历找要删除的节点
        while (node != null) {
            if (node.getElement().compareTo(deleteNode.getElement()) < 0) {
                parent = node;
                node = node.getRight();
            } else if (node.getElement().compareTo(deleteNode.getElement()) > 0) {
                parent = node;
                node = node.getLeft();
            } else {
                // 找到了，合并子节点
                // ~~1. 方式一（现在用的）~~用一个 节点暂存 一下 node，如果 node 是叶子节点，删完变 Null，下边没办法判断了
                // ~~2. 方式二（这里没有使用）mergeTwo~~
                Node<V> temp = node;
                node = mergeTwoTreebyparent(node);
                // 前面判断过了删除的为根节点的情况，node 初始值为 root，root 不为 null，到这里 parent 肯定不会为 null 了，
                assert parent != null;
                if (parent.getElement().compareTo(temp.getElement()) < 0) {
                    parent.setRight(node);
                } else {
                    parent.setLeft(node);
                }
                if (node != null) {
                    node.setParent(parent);
                }
                // 这里之后不会循环，所以改变后要链式重新计算高度
                parent.chainedReComputerHeight();
                // 找到节点，删除结束，
                // 从 parent kai shi, 判断不平衡开始
                Node<V> pparent = parent.getParent();
                while ((pparent = parent.getParent()) != null) {
                    parent = rotateInDelete(parent);
                    if (pparent.getElement().compareTo(parent.getElement()) < 0) {
                        pparent.setRight(parent);
                    } else {
                        pparent.setLeft(parent);
                    }
                    pparent.reComputerHeight();
                    parent.setParent(pparent);
                    parent = pparent;
                }
                // 这里 赋值 可以省去
                parent = rotateInDelete(parent);
                // 退出循环
                break;
            }
        }
        // 根节点可能变了，往上寻找根节点（前面判断了删除的可能是根节点的情况，这里肯定还在树中）
        while (root.getParent() != null) {
            root = root.getParent();
        }
        System.out.println(root.getElement());
        return root;
    }

    /**
     * 通过判断高度差，以及判断左右子节点的高度大小，判断三节点
     *
     * @param root 根节点，可能的不稳定点
     * @return 平衡后~~端~~的树的根节点
     */
    public Node<V> rotateInDelete(Node<V> root) {
        if (root == null) {
            return root;
        }
        // 大于二才有三节点，才可能不平衡
        // 且这样，下边高度高的，肯定三个节点都有，不会报错
        if (root.getHeight() > 2) {
            // 不平衡
            // 判断第二节点
            if (getHeight(root.getLeft()) - getHeight(root.getRight()) == 2) {
                // 左节点为第二节点
                // 右节点更高
                if (getHeight(root.getLeft().getLeft()) < getHeight(root.getLeft().getRight())) {
                    // 左节点的右节点为第三~~阶段~~节点
                    // LR
                    root = doubleWithLeft(root);
                }
                // 高度相同或左节点更高（单旋操作简单，优先级更高，所以高度相等也执行下边代码）
                else {
                    // LL
                    root = rightRotate(root);
                }
            } else if (getHeight(root.getRight()) - getHeight(root.getLeft()) == 2) {
                // 右节点为第二节点
                if (getHeight(root.getRight().getRight()) < getHeight(root.getRight().getLeft())) {
                    // RL
                    root = doubleWithRight(root);
                } else {
                    // you jie dian de 右节点为第三~~阶段~~节点
                    // RR
                    root = leftRotate(root);
                }
            }
        }
        return root;
    }

    /**
     * 传入元素方式插入
     *
     * @param element 要插入的新节点的元素
     */
    public void insertElement(V element) {
        insertNode(new Node<>(element));
    }

    /**
     * 对外暴露的插入节点方法
     *
     * @param newNode 要插入的新节点
     */
    public void insertNode(Node<V> newNode) {
        if (newNode == null) {
            return;
        }
        if (root == null) {
            this.root = newNode;
            return;
        }
        // 这两个方法也可以写一起
        // 插入新节点
        insertNode(this.root, newNode);
        // 重新平衡树
        this.root = balanceTree(newNode);
    }

    /**
     * 从某引起不平衡的节点逐步往上寻找不平衡点，然后重新平衡它
     *
     * @param leafNode 引起不平衡的叶子节点
     * @return 平衡后的树的根节点
     */
    private Node<V> balanceTree(final Node<V> leafNode) {
        // 初始设为 leaf 的 parent
        Node<V> node = leafNode.getParent();
        if (node == null) {
            return leafNode;
        }
        // 需要在旋转后使用 parent 重新指向新的根节点
        Node<V> parent;
        // 最终退出循环时：node 为 根节点
        while ((parent = node.getParent()) != null) {
            // 根据 node 和 leafNode 判断是否稳定，以及确定三节点后旋转，。
            // 旋转方法中已经重新计算了高度，返回的就是重新计算过的，只赋值就好，
            node = rotate(node, leafNode);
            // 前面得到的 parent 是 getParent 得到，本身也不知道 node 是哪边的，
            // //重新判断后设置新子树根节点
            if (parent.getElement().compareTo(node.getElement()) < 0) {
                parent.setRight(node);
            } else {
                parent.setLeft(node);
            }
            // 前面 parent 做 set 了 ，这里重新计算高度
            parent.reComputerHeight();
            // 设置 新子树根节点的 parent
            node.setParent(parent);
            // 问题记录，前面如果没有 parent.reComputerHeight();，然后后边 node 变为这个 parent，
            // 然后前面 rotate 没有做旋转，再到下边 node.reComputerHeight 就会产生作用，
            // 本来是应该没用的，因为在前面 rotate 里已经 reComputer 过了，没有想到稳定没执行到的问题，。
//            System.out.println("old node height: " + node.getHeight());
//            int oldHeight = node.getHeight();
//            node.reComputerHeight();
//            int newHeight = node.getHeight();
//            System.out.println(oldHeight == newHeight);
//            System.out.println("new node height: " + node.getHeight());
            // 继续往下进行
            node = node.getParent();
        }
        // root 为根节点，进行最后一次稳定判断，以及旋转平衡
        node = rotate(node, leafNode);
        return node;
    }

    private Node<V> rotate(Node<V> node, Node<V> leafNode) {
        // leafNode 在右边
        if (node.getElement().compareTo(leafNode.getElement()) < 0) {
            if (node.getRight().getHeight() - getHeight(node.getLeft()) == 2) {
                if (node.getRight().getElement().compareTo(leafNode.getElement()) < 0) {
                    // RR
                    node = leftRotate(node);
                } else {
                    // RL
                    node = doubleWithRight(node);
                }
            }
        }
        // newNode 在左边
        else if (node.getLeft().getHeight() - getHeight(node.getRight()) == 2) {
            if (node.getLeft().getElement().compareTo(leafNode.getElement()) < 0) {
                // LR
                node = doubleWithLeft(node);
            } else {
                // LL
                node = rightRotate(node);
            }
        }
        return node;
    }

    private int getHeight(Node<V> node) {
        return node == null ? 0 : node.getHeight();
    }

    /**
     * 插入节点，需要保证二者不为空，内部没有判断，存在空会出错
     *
     * @param root    根节点
     * @param newNode 要插入的节点
     */
    private void insertNode(Node<V> root, Node<V> newNode) {
        while (root != null) {
            newNode.setParent(root);
            if (root.getElement().compareTo(newNode.getElement()) < 0) {
                root = root.getRight();
            } else {
                root = root.getLeft();
            }
        }
        if (newNode.getParent().getElement().compareTo(newNode.getElement()) < 0) {
            newNode.getParent().setRight(newNode);
        } else {
            newNode.getParent().setLeft(newNode);
        }
        newNode.chainedReComputerHeight();
    }

    /**
     * 左旋
     *
     * @param root 不稳定节点
     * @return 左旋后根节点
     */
    private Node<V> leftRotate(Node<V> root) {
        if (root == null || root.getRight() == null) {
            return root;
        }
        Node<V> tempRoot = root.getRight();
        Node<V> left = tempRoot.getLeft();
        root.setRight(left);
        //  注意每次 set 后的重新计算
        // 这里包含了中间节点变叶子节点时 的变化，如 这里指向空节点，高度就回到了1，
        root.reComputerHeight();
        if (left != null) {
            tempRoot.getLeft().setParent(root);
        }
        tempRoot.setLeft(root);
        tempRoot.reComputerHeight();
        root.setParent(tempRoot);
        tempRoot.setParent(null);
        return tempRoot;
    }

    /**
     * 右旋
     *
     * @param root 不稳定节点
     * @return 右旋后根节点
     */
    private Node<V> rightRotate(Node<V> root) {
        if (root == null || root.getLeft() == null) {
            return root;
        }
        Node<V> tempRoot = root.getLeft();
        Node<V> right = tempRoot.getRight();
        root.setLeft(right);
        root.reComputerHeight();
        if (right != null) {
            tempRoot.getRight().setParent(root);
        }
        tempRoot.setRight(root);
        tempRoot.reComputerHeight();
        root.setParent(tempRoot);
        tempRoot.setParent(null);
        return tempRoot;
    }

    /**
     * 双旋
     *
     * @param root 不稳定节点
     * @return 双旋后的根节点
     */
    private Node<V> doubleWithRight(Node<V> root) {
        Node<V> right = rightRotate(root.getRight());
        root.setRight(right);
        // 这个重新计算好像可以省略，会被下边 右旋中的重新计算给覆盖
        root.reComputerHeight();
        right.setParent(root);
        return leftRotate(root);
    }

    /**
     * 双旋
     *
     * @param root 不稳定节点
     * @return 双旋后的根节点
     */
    private Node<V> doubleWithLeft(Node<V> root) {
        Node<V> left = leftRotate(root.getLeft());
        root.setLeft(left);
        // 这个重新计算好像可以省略，会被下边 右旋中的重新计算给覆盖
        root.reComputerHeight();
        left.setParent(root);
        return rightRotate(root);
    }
}
